There are numerous communication systems wherein a plurality of users communicate with each other on a communications loop or ring. For the purpose of this discussion, the term "user" encompasses the computers, the peripheral input/output devices, the computer terminals and the various interfacing equipment that may be found in a computing environment. A major problem in the prior art arises when a large number of users having different delay constraints are linked together in a network for sending and receiving data. For example, difficulties arise when one combines on a network high-speed digital data communications between computers and a relatively low-speed digitized voice connection. It is difficult to combine high-speed data and low-speed data when users with different transmission-delay constraints are linked in a loop configuration.
More specifically, the users of a TDM ring are divided into groups, each of which is represented on the ring by a node. Generally, users that are located in close proximity to one another are grouped together. The nodes of the ring are arranged in a loop such that information flows from one node to the next and in one direction around the loop. A transmission medium is used to physically link the nodes and each node has one input port and one output port for the ring. Within a group, each user of the group is physically linked to the node in such a way that information flows to and from the user and the node through a transmission medium.
In the TDM ring framework, there are no direct physical links between users. The flow of information between users is routed through the appropriate nodes that lie between the users. The routing comprises an indirect link between users and is termed a "connection" for the purpose of this discussion. Various techniques, or protocols, have been formulated to initiate such connections between users, manage the information flow in the connections, and terminate connections. These protocols generally organize the information flowing in each connection into packets and provide a means for identifying each packet, e.g., giving each packet an address label, that allows the packet to be routed to the correct destination.
Important attributes of a connection are connectivity type, information bandwidth, and packet-delivery time. Of the connectivity-types, point-to-point and multi-point connections are two examples. The first is a connection between two users wherein information flows to and from each user and the second is a connection in which the information flows from one user to several other users in a one-way direction. The bandwidth of the connection refers to the amount of information that flows through the connection during a given amount of time. The packet-delivery time refers to the time it takes for a packet to reach its destination. This time can range in value, depending on the number of users seeking access to the TDM ring. Generally, the information in a communication system is managed by allowing each connection a certain number of packets to be routed in a given amount of time. In the generic TDM system, a number of time-slots are grouped together to form a frame. Each time-slot has a specific location in the frame and carries one packet of information for a specific connection. The frame is continuously repeated around the ring whereby new data is supplied in each time-slot during each frame repetition. For a point-to-point connection between two users, both a packet from the first user to the second user and a response packet from the second user to the first user can be sent within one frame.
One node is temporarily or permanently assigned the responsibility of preserving the time-slot order and the integrity of the frame on the ring. The node is usually referred to as the master node and all other nodes are correspondingly referred to as slave nodes.
Each node contains mapping information which, on a temporary or permanent basis, associates each time-slot with data to be transmitted to or received from a particular user. The combined mapping information in all nodes determines the logical connections established throughout the ring. Such connections may be either point-to-point or multipoint.
Conventionally, the master node contains a first-in-first-out (FIFO) buffer memory, the input of which is connected to the receive port of the master node, and the output of which is connected to the transmit port. A number of consecutive time-slots are stored in the buffer. The master node selects the number of time-slots such that data received on a particular time-slot location in the received frame is transmitted on the same time-slot location in the transmitted frame. In some systems, the master node will hold up the transmission of time-slots so as to preserve the integrity of a given frame being transmitted from the master node onto the ring. Accordingly, the number of time-slots stored in the buffer may vary with time and system configuration.
The time delay from when a node transmits a particular time-slot to when the same node is again ready to transmit the same time-slot is often defined as the latency of the ring or, simply, the ring latency. The definition holds for both master nodes and slave nodes. Although the above definition is stated in terms of time-delay, ring latency can be measured in time-slots and in frames as well (i.e., the number of time-slots or frames encountered between transmission and reception). The latency of the ring can be divided into two different components. The first component is the transmission latency and it is defined as the time a particular time-slot spends in the transmission medium that links the nodes and the time it spends in all the slave nodes. The second component is the buffer latency and it is defined as the time spent in the FIFO buffer of the master node.
In a typical TDM ring, the master node will adjust the number of time-slots stored in its FIFO buffer so as to make the ring latency equal to an integer number of frames. The master node will use the FIFO buffer to compensate for any fractional amount in the above defined first component of latency by delaying the transmission of the next time-slot from the FIFO buffer. The incorporation of latency compensation into the ring increases the utilization of the ring and the adjustment of the ring latency to an integer number of frames insures that no time-slots are lost on the ring.
The repetition rate of the frame around the ring is determined by the transmission time allowed for a time-slot multiplied by the total number of time-slots. The resulting bandwidth of a connection on the TDM ring is one packet per frame period (for example, see FIG. 3). The delay incurred in delivering a packet for a given connection will range from one time-slot-transmission delay to the latency of the ring (usually one or two frame periods), depending upon when the information was delivered to the node with respect to the position of the frame and where the particular source and destination nodes are located on the ring. For the successful transfer of information, a connection often will require that at least a predetermined minimum amount of bandwidth be provided, or that no more than a certain amount of delay occur between adjacent packets for a given connection, or both of these specified amounts.
The utility and success of a TDM ring not only depends on the ability of the system to provide successful connections given the delay tolerance of ring users but also on the ability of the system to support a large volume of connections for system flexibility. A major problem arises in the prior art in meeting these two conflicting goals. In the prior art, providing high bandwidth and short packet delays requires a short frame. A short frame, however, limits the total number of time-slots and, hence, connections. Thus, combining a large number of high-speed and low-speed connections, each having different transmission-delay requirements, in a TDM ring is difficult.
For example, a frame may include a plurality of contiguous time-slots, 1-N, for carrying data and a header, H, for marking the beginning of each frame. The header carries a prearranged data pattern and is used by each node to identify the individual time-slots by counting the number of time-slots received after receipt of the header. Since the support of each connection requires one or more time-slots, a frame containing many time-slots will allow a larger number of connections to be supported. However, a long frame containing many time-slots will result in higher ring latency or delay. Conversely, a short frame containing fewer time-slots will enable a smaller number of devices to be connected to the ring. However, a short frame has the advantage of reducing the ring latency.
To increase the bandwidth for a specific connection, one method in the prior art allocates more than one time-slot per frame for one or more given connections. The additional allocation leads to greater bandwidth for the connection when the protocol for the information flow does not need an acknowledgment from the destination user within one ring latency delay (e.g., batch file-transfer operations). Protocols requiring acknowledgments in less than one frame delay will not benefit from additional time-slots per connection as these protocols must wait one frame delay for the acknowledgment from the destination user.
In one case, the addition of time-slots dedicated to a specific connection also serves to reduce the delivery time for a packet. In a point-to-point connection where the first user is closer to the transmit port of the master node than the second user, the first user can use the additional time-slots per frame to reduce the packet-delivery time to the second user. The corresponding response packets from the second user, however, pass through the FIFO buffer of the master node and are delayed by a significant amount of time, up to an amount equal to the ring latency. The additional time-slots reduce packet-delivery times in one direction but not in the other. Therefore, combining a large number of high-speed and low-speed connections, each having different transmission-delay requirements, in a TDM ring remains as a difficult task.